//
//  _是否是完全二叉树.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/2/6.
//

import UIKit
// 使用层序遍历
class IsCompareTree: NSObject {
    func isCmpare(_ node: TreeNode<Int>?) -> Bool {
        guard let node = node else {
            return true
        }
        var queue = [TreeNode<Int>]()
        queue.append(node)
        while !queue.isEmpty {
            let item = queue.removeFirst()
            if let left  = item.left, let right  = item.right {
                queue.append(left)
                queue.append(right)
            } else if let _ = item.left, item.left == nil {
                return false
            } else if let left = item.left, item.right == nil{ // 之后的几点必须都是叶子节点，或是queue中没有节点
                queue.append(left)
                break
            } else {
                break
            }
        }
        if queue.isEmpty {
            return true
        } else {
            for node in queue {
                let result = !node.isLeafNode()
                if result {
                    return false
                }
            }
        }
        return true
    }
    func isCmpare1(_ node: TreeNode<Int>?) -> Bool {
        guard let node = node else {
            return true
        }
        var queue = [TreeNode<Int>]()
        queue.append(node)
        var status = false
        while !queue.isEmpty {
            let node = queue.removeFirst()
            if node.left == nil && node.right != nil {
                return false
            }
            if status && !isLeaf(node) {
                return false
            }
            if (node.left != nil && node.right == nil) || isLeaf(node) {
                status = true
            }
            
            if let left = node.left {
                queue.append(left)
            }
            if let right = node.right {
                queue.append(right)
            }
        }
        return true
    }
    func isLeaf(_ node: TreeNode<Int>) -> Bool {
        return node.left != nil && node.right != nil
    }
}
